﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Airplane
    {
        public Airplane()
        {
            //입력
            int n = GetConsole.GetInt();
            int k = GetConsole.GetInt();
            List<Point> pointList = new List<Point>();
            pointList.Add(new Point(0, 0, 0)); // 시작점 추가
            while (n-- > 0)
            {
                Point p = new Point();
                p.x = GetConsole.GetInt();
                p.y = GetConsole.GetInt();
                p.startRange = GetRange(pointList[0], p);
                pointList.Add(p);
            }
            pointList.Add(new Point(10000, 10000, 200000000)); // 끝점 추가
            //처리
            //시작점에서 가까운 순으로 정렬
            pointList = pointList.OrderBy(p => p.startRange).ToList();
            //주행 거리 리스트 생성
            List<Course> courseList = new List<Course>();
            for (int i = 1; i < pointList.Count; i++)
            {
                courseList.Add(new Course(0, i, pointList[i].startRange));
                for (int j = i + 1; j < pointList.Count; j++)
                {
                    courseList.Add(new Course(i, j, GetRange(pointList[i], pointList[j])));
                }
            }
            //거리순으로 정렬
            courseList = courseList.OrderBy(c => c.range).ToList();
            bool findCourse = true;
            int index = courseList.Count / 2;
            int half = index;
            while (half > 0)
            {
                findCourse = GetCourse(courseList.GetRange(0, index + 1), k, pointList.Count - 1);
                half = half / 2;
                if (findCourse)
                {
                    index = index - half;
                }
                else
                {
                    index = index + half;
                }
            }
            double sqrtValue = courseList[index].range;
            sqrtValue = Math.Sqrt(sqrtValue);
            int liter = (int)sqrtValue / 10 + 1;
            Console.WriteLine(liter);
            GetConsole.GetInt();
            
        }
        public bool GetCourse(List<Course> courseList, int k, int lastPoint)
        {
            List<int> prevList = new List<int>();
            prevList.Add(0);
            for (int i = 0; i < k + 1; i++)
            {
                List<int> nextList = new List<int>();
                foreach (int n in prevList)
                {
                    List<Course> startValueList = courseList.FindAll(c => c.from == n);
                    nextList.AddRange(startValueList.Select(c => c.to).ToList());
                }
                if (nextList.Contains(lastPoint))
                { return true; }
                prevList.Clear();
                prevList.AddRange(nextList);
            }
            return false;
        }
        public struct Point
        {
            public int x;
            public int y;
            public int startRange;
            public Point(int newX, int newY, int newStartRange)
            {
                x = newX;
                y = newY;
                startRange = newStartRange;
            }
        }
        public struct Course
        {
            public int from;
            public int to;
            public int range;
            public Course(int newFrom, int newTo, int newRange)
            {
                from = newFrom;
                to = newTo;
                range = newRange;
            }
        }

        private int GetRange(Point from, Point to)
        {
            return GetRange(from.x, from.y, to.x, to.y);
        }
        private int GetRange(int fromX, int fromY, int toX, int toY)
        {
            int x = toX - fromX;
            int y = toY - fromY;
            return (x * x) + (y * y);
        }
    }
}
